Practice Problems and Solutions 08 -- The Maybe Monad

You should do these problems on paper or mentally first, and only THEN check the solution.

In this tutorial we take the Maybe monad as an example, and develop the entire monad framework in terms of the Maybe type.

The Maybe type is a way of dealing with errors and exceptions in computations. This is a special case of the general reason for monads: how do we separate out the complexity of a computation into foreground and background activity, so that we can focus on the foreground while being precise about the whole background context? A useful idea, but how to make use of it in a comprehensive and easy-to-understand way? What happens if we want to represent everything (including functions) using Maybe type?

Two familiar issues will guide us throughout:

(A) How do we replace a bunch of tedious, almost-identical pieces of code with an abstraction?

(B) How do we fit this abstraction into the "Haskell Ecosystem" via a type class?

The Maybe data type is defined as follows:

data Maybe a = Just a | Nothing deriving (Show, Eq)

8.1. The first thing we have to do is make this data type an instance of the Functor class by defining a function fmap on it. Fill in the blanks to create the appropriate instance (there is really only one way to do this according to the types): 

instance Functor Maybe where
    -- fmap :: (a -> b) -> Maybe a -> Maybe b
    fmap f Nothing = undefined
    fmap f (Just x) = undefined

Show Solution

8.2. Evaluate: fmap (*3) (Just 3)

Show Solution

8.3. Evaluate: map (fmap (length)) [Just [], Nothing, Just [2,3]]

Show Solution

8.4. Define a function (using fmap) which adds 1 to a Maybe Integer. Here is the type: 

inc :: Maybe Integer -> Maybe Integer

Show Solution

8.5. Define a function (using fmap) which determines if a Maybe Integer is even. Here is the type: 

evenm :: Maybe Integer -> Maybe Bool

Show Solution

8.6. Now define a function which adds two Maybe Integers, without using fmap. Just consider all the input patterns. Do not use a case expression. Here is the type: 

plus :: Maybe Integer -> Maybe Integer -> Maybe Integer

Show Solution

8.7. Now define a function which divides two Maybe Integers, without using fmap. Just consider all the input patterns and return Nothing if a "divide by zero" error would occur. Do not use a case expression. Here is the type: 

divide :: Maybe Integer -> Maybe Integer -> Maybe Integer

Show Solution

8.8. Now give a different definition for plus, which does not evaluate the second argument if the first one is Nothing. Hint: use two case expressions and consider the arguments one at a time.

Show Solution

8.9. Do the same as for 8.8 but for the divide function.

Show Solution

This can get a little extreme (see the lecture slides from Monday 3/4), so we need to abstract out the common pattern, as usual, and find a better way to write this.

Two observations before we think about this:

(1) We need to deal with the fact that Haskell thinks of all functions as curried, i.e., having a single parameter and perhaps returning a function as output (if there is more than 1 parameter).

(2) Functions generally don't want to take Maybe values as input, but sometimes DO produce Maybe values as output, because something goes wrong in the algorithm. A good example is Map.lookup: 

 Data.Map.lookup :: Ord k => k -> Map k a -> Maybe a
So the type of a curried function which may find exceptional conditions during computation is: 

      f :: a -> Maybe b



 Also, note that any normal function can just wrap
 its output in Just to satisfy this type. This is a very common
operation in a monad (inserting a foreground value into a basic background context), so
we'll define a function to do this. 



8.10. Write a function return which takes a Integer and wraps it in a Just;
	its type is

return :: Integer -> Maybe Integer




Show Solution 




 For the next few problems, we will consider a situation where we
	want to manipulate natural numbers, so that negative numbers would be
	considered an error, and any computation accepting a natural number and producing a negative number
	would result in a Nothing.



8.11. Write a function which takes an Integer, increments it, and returns
	the result as a Maybe type by just wrapping it in a Just; use the
	function return to do this; the
	type is

incm :: Integer -> Maybe Integer




Show Solution 




8.12. Write a function which takes an Integer, decrements it, and 
	and returns Nothing if the input is 0, and otherwise uses return to wrap the result in a Just; the
	type is

decm :: Integer -> Maybe Integer




Show Solution 





 One more observation: (3) in a long sequence of steps in a computation where
	failure (represented by Nothing) can occur, 
 we can generally think of it in terms of starting
 with an input value, and a series of Maybe values:

     a => Maybe b => Maybe c => Maybe d ->  ...  



So here's the point after considering (1), (2), & (3):
How do we deal with a sequence of Maybe values which are
 acted on by functions of the type a -> Maybe b ?




 The solution Haskell adopts for this situation
 focusses on two principal functions: return and bind.
You've already seen return, so let's think about bind, which
is represented by the infix operator >>=. 





8.13. Write the implementation of bind, whose type is

(>>=) :: Maybe Integer -> (Integer -> Maybe Integer) -> Maybe Integer


Bind "unwraps" its first argument, and applies its second argument to this
unwrapped value. When a Nothing comes in, a Nothing should come out, no matter
what the function is. Hint: given the type, there is only one way to write this!




Show Solution 





8.14. Describe the result of the following function and evaluate (f 4)

f :: Integer -> Maybe Integer
f x = (return x) >>= incm






Show Solution 





8.15. Describe the result of the following function and evaluate (f' 0)

f' :: Integer -> Maybe Integer
f' x = (return x) >>= decm






Show Solution 




8.16. Write a function f which adds 3 to a Integer input, using
	ONLY return, bind, and incm; its type is

f :: Integer -> Maybe Integer






Show Solution 




8.17. Write f as in the last problem, but without using return.
	Hint: Instead of wrapping and then unwrapping in the first two steps, just use the
	input value directly. 

f :: Integer -> Maybe Integer






Show Solution 







8.19. Give a (anonymous) lambda expression which is equivalent to the function incm.




Show Solution 




8.20. Replace the second and third occurrences of incm in the 
	definition of f by anonymous lambda expressions (rename each of these
	so they do not use the variable x).




Show Solution 




8.21. Give the scope of the variables x, y,  and z in the
	previous definition of f




Show Solution 




8.22. Replace the expression \z -> return (z+1) by a lambda
	expression \z -> .... which adds together the values from y and z. Note: this will
	be possible because of the scope of y and z. 




Show Solution 




8.23. Now define a function plusm,  with a type of 

plusm :: Integer -> Integer -> Maybe Integer


Hint: use return!




Show Solution 




8.24. Now, in the definition in 8.22, replace
	the expressions involving return with expressions involving incm
	and plusm. What does this function do?




Show Solution 




8.25. Now  remove the parentheses (this will work because of the precedence and
	associativity of lambda expressions and bind). 




Show Solution 




8.26. Now rearrange the expression so that there is a newline after each -> , 
	and line up the expression neatly. Indicate the scope of each of x, y, and z again. 




Show Solution 




 Creating the polymorphic Maybe type in Haskell.  



 In order to make the Maybe type a monad and a part of the "Haskell Ecosystem" (objective (B)
	at the top of this document), we have to define the functions return and bind
	as part of an instance declaration for the Monad type class.




8.27. Fill in the function definitions in the following instance declaration to create the polymorphic
	Maybe monad:

instance Monad Maybe where

  -- return :: a -> Maybe a
  
  -- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b







Show Solution 




 The principle advantage of making a type a monad is that we can
	use the do notation to write computations which have
	an imperative-language feel, using something like assignment statements,
	but with complete control over the foreground and background computations. 



 The do notation permits us to turn the expression from 8.26, i.e.,

     f x = incm x >>= \y ->  
           incm y >>= \z ->  
           plusm y z


into

     f x = do y <- incm x  
              z <- incm y  
              plusm y z







8.28. Give the do expression corresponding to the following bind expression:

g :: Integer -> Maybe Integer
g x = incm x >>= \y -> incm y >>= \z -> plusm z y 

	




Show Solution 




8.29. Rewrite this last do expression using return instead of plusm
	in the last line. Hint: look back at the definition in 8.23. 	




Show Solution 




8.30. Give the bind version of the very last ("redundant") definition of g.	




Show Solution 




 Note that in these examples, as long as the right side of the <-
is a Maybe type, it will be "unwrapped" properly to bind the left side. 
 In these next problems, all the right side expressions are Maybe Integer.



8.31. Evaluate  (weird 1) using the following definition:

weird :: Integer -> Maybe Integer
weird x = do y <- if x < 10 then return 4 else incm 8         
             z <- Just 7
             w <- (\a -> Just (a + z)) y
             v <- let b = y * z in return (b+1)
             plusm v w

	




Show Solution 




8.32. Evaluate  (strange 1) using the following definition:

strange :: Integer -> Maybe Integer
strange x = do y <- do x1 <- Just x
                       y2 <- return 8
                       plusm x1 y2
               z <- case incm y of
                      Nothing -> Nothing
                      Just n -> return n
               plusm y z

	




Show Solution 




 In fact, you can do ANYTHING you want on
the right side of the "assignment statements"in the do expression,
as long as it evaluates to a Maybe type, and the binding made
matches the type inside the Maybe.  The value of the whole
	expression is given by the last line, so that has to
	type-check; otherwise, since Maybe is polymorphic, you
	can use any kind of Maybe type in the middle of the do expression.
	That is, if you have a do expression which is a (Maybe someType),
	

ex :: Maybe someType
ex = do x1 <- expr1
        x2 <- expr2
          ...
        xk <- exprk
          ...
        finalExpr


then finalExpr must have type (Maybe someType), but in each line
all that is required is 

      xk <- exprk
	  
      ^       ^
      |       |
   type aType    type (Maybe aType)


As long as the types match in the various expressions, all will be well. 


8.33. Evaluate  (mixed 9) using the following definition:

isEven :: Integer -> Maybe Bool
isEven x = Just (x `mod` 2 == 0)

mixed :: Integer -> Maybe Integer
mixed x = do y <- plusm x 6
             b <- even y
             return $ if b then x else 2 * x

	




Show Solution 




8.34. Evaluate  (bizarre 1) using the following definition:


bizarre :: Integer -> Maybe Integer
bizarre x = do b <- do x1 <- if x < 10 then Just True else Nothing
                       y1 <- Just False
                       return (x1 && y1)
               y <- if b
                       then return 1
                       else return 10
               incm y

	




Show Solution 





Patterns in Do expressions



Because lambda expressions can use patterns, we can also use them in do expressions. 



8.35. Translate the following definition into one that uses a do expression:

h :: Integer -> Integer  -> Maybe (Integer,Integer)
h x y = return (x+1,y-1) >>= \(x1,y1) -> return (x*2,y*3) >>= \(x2,y2) -> return (y2,x2)

	




Show Solution 




8.36. Evaluate h 1 2.	




Show Solution 




8.37. Evaluate  showIt 5 given the definitions:

split' :: Integer -> Maybe (Integer, Integer)
split' x = Just (x, x `div` 2)

showIt :: Integer -> Maybe Integer
showIt x = do (y1,y2) <- Just (3,4)
              (z1,z2) <- split' x
              return (y1*z1+y2*z2)

	




Show Solution 




 You can also use underscore patterns, which throw away their values. Consider the following
definitions:


isEven :: Integer -> Maybe Integer
isEven n | n `mod` 2 == 0 = Just n
         | otherwise      = Nothing

-- This shows how you can return
-- the value if it passes the test:

example x = do y <- incm x
               z <- isEven y
               plusm x y




8.38. Evaluate (example 5) and (example 10)




Show Solution 




But since you don't use the value in z (it just passes
	along its input), you can just pattern match on a wildcard _ . 



example' x = do y <- incm x
                _ <-isEven y
                plusm x y




But do notation allows you to leave out the "z <-" or "_ <-"
as long as the expression listed on a line by itself
returns the appropriate type; here all it does is
test if y is even and force a Nothing if it is not. 



example'' x = do y <- incm x
                 isEven y
                 plusm x y





This is essentially a "filter" which will produce a Nothing in the second
line if the predicate is not satisfied. 



One more feature!  You can make local definitions in a do expression.
These allow you to create local definitions in the foreground using a let. The scope
of the binding is the rest of the do expression.



8.39. Evaluate (lastExample 1) using the following definition:

lastExample :: Integer -> Maybe Integer
lastExample x = do y <- incm x
                   let z = 2 * y           -- notice that this takes place in foreground (Integer)
                   w <- incm z
                   let v = w * z           -- there are no (Maybe Integer) values involve in a local let
                   return $ v * 3






Show Solution